Basic arithmetic operations such as addition, multiplication, and inversion performed modulo a prime number p have numerous applications to cryptographic systems. For example, encryption, decryption, or key exchange in Rivest-Shamir-Adelman (RSA), Diffie-Hellman (DH), Digital Signature Standard (DSS), and elliptic curve cryptographic systems all use modular arithmetic operations. These cryptographic systems are described in, for example, W. Diffie and M. E. Hellman, “New Directions in Cryptography,” IEEE Trans. Information Theory, vol. 22, pp. 644–654 (1976); B. S. Kaliski Jr., “The Montgomery Inverse and Its Applications,” IEEE Trans. Computers, vol. 44, pp. 1064–1065 (1995); J. J. Quisquater and C. Couvreur, “Fast Decipherment Algorithm for RSA Public-Key Cryptosystem,” Elect. Lett., vol. 18, pp. 905–907 (1982); and “Digital Signal Standard (DSS),” Fed. Reg., vol. 56, p. 169 (1991).
Modular arithmetic is typically performed on a set Zp of integers, referred to as a “complete residue” set that is generally defined as, for a selected prime number p, the set of integers 0, 1, 2, 3, . . . , p-1. A complete residue set Zp is closed with respect to the operations of addition and multiplication, i.e., the sums and products of any elements of the complete residue set Zp are also elements of the complete residue set Zp. In addition, each element of Zp has a multiplicative inverse that is also an element of the complete residue set Zp.
Multiplication and addition on the complete residue set Zp are similar to standard multiplication and division, but are performed modulo the prime number p. For example, the modular product a·b (mod p) is obtained by calculating the product a·b, and then dividing by p one or more times to obtain a remainder that is an element of the complete residue set Zp. As a specific example, the product of integers a=5, b=6 computed modulo-p for p=11, is a·b=5·6 (mod 11)=30 (mod 11)=8. The modular inverse a−1 of an element a of Zp is the element of Zp such that a·a−1=1 (mod p). As a specific example, for a=6, p=11, a−1=2 because 6·2 (mod 11)=1.
Many important cryptographic systems require a substantial number of modular multiplications and computations of modular multiplicative inverses.
As used herein, “inverse” and “inversion” refer to inverse operations with respect to multiplication. Fast, efficient multiplication and inversion methods are needed to carry out such calculations. One such method is the Montgomery method, described in P. L. Montgomery, “Modular Multiplication Without Trial Division,” Math. of Computation, vol. 44, pp. 519–521 (1985), in which integers a that are elements of the complete residue set Zp are transformed into corresponding integers A referred to as “M-residues” (also elements of Zp) according to the transformation A=a 2n (mod p), wherein the integer n is selected so that 2n−1≦p<2n. A Montgomery product MPROD of two M-residues A, B of respective integers a, b is defined as:C=MPROD(A,B)≡A B 2−n(mod p),and is the M-residue of the modulo-p product c=a b. The product c can be obtained from the M-residue product C as:c=C 2−n (mod p).
Calculation of the modular product c=ab using the Montgomery product of the M-residues A, B of a, b is typically faster than direct modular multiplication of a, b because the Montgomery product requires only divisions by two that are easily implemented as bit-shifting operations on a binary number-based digital computer.
Modular exponentiation and modular multiplicative inversion are other common operations in cryptographic systems. In many cryptographic applications, both an M-residue of c, i.e., C=c 2n (mod p) and a quantity referred to as a “Montgomery inverse” are needed. A particular Montgomery inverse c−12n (mod p) and a method for its computation are discussed in B. S. Kaliski Jr., “The Montgomery Inverse and Its Applications,” cited above. This Montgomery inverse is referred to as a “Kaliski inverse” KINV( ) herein. With reference to Table 1, the Montgomery inverse KINV(a) is obtained by first calculating an intermediate value a−1 2k (mod p) in a phase I, and then correcting this intermediate value to obtain the Montgomery inverse KINV(a)=a−12n (mod p) in a phase II.
TABLE 1Pseudocode for determination of a Montgomery inversePHASE Iinput a, p, wherein 1 ≦ a ≦ p−1u = p; v = a; r = 0; s = 1k = 0while (v > 0)if u is even then u = u/2, s = 2selse if v is even then v = v/2, r = 2relse if u > v then u = (u−v)/2, r = r+s, s = 2selse if v ≧ u then v = (v−u)/2, s = s+r, r = 2rk = k + 1if r ≧ p then r = r−preturn r = a−12k (mod p), and k, wherein n ≦ k ≦ 2nPHASE IIInput r, k, p (from PHASE I)for I = 0 to I = k−n, doif r is even then r = r/2else then r = (r+p)/2x = rreturn x, wherein 1 ≦ x ≦ p − 1 and x = a−12n (mod p)
Unfortunately, obtaining a Montgomery product MPROD or a Montgomery inverse KINV( ) using the Montgomery product typically requires transforming numbers expressed as elements of the complete residue set Zp to and from their respective M-residues. These transformations make such calculations slow and expensive. In addition, because cryptographic systems often require many modular multiplications, the speed and efficiency of such calculations can limit the utility of a cryptographic system. Hence, improved methods and apparatus are needed for obtaining Montgomery products and Montgomery inverses.